The present invention relates to a method and system of real-time graphical simulation of large rotational deformation and manipulation using modal warping. More particularly, this invention relates to a method and system of real-time graphical simulation of large rotational deformation and manipulation, in which both position and orientation constraints are implemented in a straightforward manner to simulate large bending and/or twisting deformations with acceptable realism.
I. Introduction
Everything in this world deforms. In many objects or creatures, deformation is such a conspicuous characteristic that their synthetic versions look quite unnatural if the deformation process is not properly simulated. Therefore, modeling of deformation is an important aspect of computer animation production. The invention presents a physically-based method and system for dynamic simulation of deformable solids, attached to rigid supports and excited by their rigid motions and/or external forces such as gravity. The proposed technique makes a significant improvement in simulation speed, while maintaining the realism to a sufficient level, even for large deformations.
It is a well-established approach to model elastic solids as continuums and solve their governing equations numerically using finite element methods. When adopting a continuum model, it is necessary to choose the measure of strain that quantifies deformation. Green's strain tensor, which consists of linear terms and a nonlinear term, has been a common choice for large deformations. Unfortunately, time stepping of the resulting nonlinear system can be computationally expensive, hampering its practical use in animation production.
The computational load can be reduced remarkably by employing modal analysis based on a linear strain tensor. In this technique, a set of deformation modes—a small number of principal shapes that can span free vibration of the elastic model—is identified and precomputed. Then, the problem of simulating deformation is transformed to that of finding the weights of the modes, which results in a significant reduction in computational complexity. This technique can also synthesize geometrically complex deformations with negligible main CPU costs on programmable graphics hardware.
However, modal analysis can produce quite unnatural results when applied to bending or twisting deformations of relatively large magnitudes. In particular, the volume of the deformed shape can increase unrealistically, as shown in FIG. 4. These unnatural results are due to the omission of the non-linear term, which is not negligible for such deformations. The invention proposes a new technique that overcomes the above limitations of linear modal analysis. As a result, the proposed technique generates visually plausible shapes of elastodynamic solids undergoing large rotational deformations, while retaining its computational stability and speed. Also, our formulation provides a new capability for orientation constraints, which has not been addressed in previous studies. The use of position/orientation constraints can create interesting animations (Section VI) which would have been difficult if orientation constraints were not provided.
The innovative aspect of our technique lies in the way of handling rotational parts of deformation in the modal analysis framework. To exploit the framework of linear modal analysis, we omit the nonlinear term during the initial setup, which corresponds to precomputing the modal vibration modes at the rest state. When the simulation is run, however, we keep track of the local rotations that occur during the deformation, based on the infinitesimal rotation tensor. Then, at each time step we warp the precomputed modal basis in accordance with the local rotations of the mesh nodes. The rest of the method is basically the same as in linear modal analysis. The above book-keeping operations—tracking local rotations and warping the modal basis—require only a small amount of extra computation. Therefore, our method can simulate dynamic deformations in real-time by employing programmable graphics hardware, but with an extended coverage of deformations.
II. Related Work
Much effort has been devoted to simulating the motion of deformable objects. Past studies in this area have had two central aims: to speed up the simulation and/or increase the realism of the result.
The speed and realism of simulations, which usually trade off each other, are heavily dependent on how the nonlinearities are handled. If realism is important, Green's quadratic strain tensor could be used, which produces realistic results even for large deformations. However, time stepping of the resulting nonlinear system can be computationally expensive. Several methods have been proposed to reduce the computational load of this approach. Lumped mass approximation diagonalizes the mass matrix so that its inverse can be computed efficiently. Further reduction of the computation time can be achieved by employing adaptive methods based on a multi-grid solver, non-nested overlapping layers of unstructured meshes, subdivision of the control lattice, or refinement of basis functions. However, the speed-up achieved by those methods is limited, because they must still deal with the inherent problems resulting from the nonlinearities. The computation time can be greatly reduced by adopting the modal analysis of linear elastodynamics, which omits the nonlinear term. Since Pentland and Williams first introduced this technique to the computer graphics community, it has been used for modeling the dynamic movements of trees in turbulent wind, and for generating sounds corresponding to the behavior of deformable objects. In particular, some researchers showed that the deformation of human skin excited by rigid body motion can be generated in real-time on programmable graphics hardware. They also proposed an output-sensitive technique for collision detections among reduced deformable models. Still another researchers addressed the manipulation constraints, and combined modal analysis with rigid body simulation to deal with free-floating deformable objects. Although modal analysis significantly accelerates the simulation, it generates noticeable artifacts when applied to large deformations due to the linearization. Here we propose a technique that eliminates the linearization artifacts while retaining the efficiency of the modal analysis.
The linearization artifacts observed in simulations based on linear modal analysis arise in large part because linear modal analysis does not account for rotational deformations. A frame of reference and modeled the deformation relative to that reference frame was introduced by some researchers. Since simulations using the reference frame capture the rotational part of the deformation, they can handle large rotational motions of deformable solids. However, large deformations within the solid are also susceptible to the linearization artifact. To realistically animate articulated deformable characters in a prior art, the character is first divided into overlapping regions, then each region is simulated separately, and finally the results are blended. For nonlinear quasi-static deformations of articulated characters, a modal displacement model equipped with a continuously articulated coordinate system was introduced in a prior art.
To address large relative rotational deformations within a single object, the stiffness warping method that tracks the rotation of each node and warps the stiffness matrix was proposed in a prior art. Our method is similar to their approach in that rotations are handled separately to reduce the linearization artifacts. The intrinsic difference is that, whereas the stiffness warping method is formulated in the original space, our method is formulated in the modal space. This results in a significant speed up in both simulation and visualization by (a) solving decoupled, reduced system of linear equations, and (b) utilizing programmable graphics hardware for vertex updates of large models. However, other prior art is based on node-wise rotation of the stiffness matrix, thus can produce a spurious ghost force when applied to a free-floating deformable object. Currently, our work is focused on a deformable object attached to a rigid support, thus the ghost force effects are suppressed by the constraint force.
Recently, datadriven tabulation of the state space dynamics and dimensional model reduction of the deformed shapes was proposed to simulate large deformations at an interactive speed with visually realistic results. Because the tabulation could not be performed for all possible system responses, they confined user interactions to certain types of movements. They reported that the precomputation for the dinosaur model shown in FIG. 10 took about 30 hours. In comparison, our method is formulated by adding simple extensions to linear modal analysis. As a consequence, it does not entail long precomputation times, nor does it restrict the types of user interactions. However, self-collisions and global scene illumination cannot be precomputed in our method.
Accordingly, a need for the invention has been present for a long time. This invention is directed to solve these problems and satisfy the long-felt need.